# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from leetcode_test import ListNode, TreeNode
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        
        def backtrack(head, root):
            # nonlocal find
            if not head.next:
                print("xx", head.val, root.val)
                return True
            if not root.left or not root.right:
                return False
            if head.val == root.val:
                if backtrack(head.next, root.left):
                    return True
                if backtrack(head.next, root.right):
                    return True
            else:
                if backtrack(head, root.left):
                    return True
                if backtrack(head, root.right):
                    return True
            return False
        s = backtrack(head, root)
        return s

if __name__ == "__main__":
    head = [4,2,8,7]
    root = [1,4,4,None,2,2,None,1,None,6,8,None,None,None,None,1,3]
    # head = [1,4,2,6,8]
    # root = [1,4,4,None,2,2,None,1,None,6,8,None,None,None,None,1,3]
    h = ListNode.create(head)
    t = TreeNode.create(root)
    print(h,t)
    print(Solution().isSubPath(h, t))

